package com.yun.algorithmproblem.leetcode;


import java.util.Arrays;

public class Leetcode2563 {

	public long countFairPairs(int[] nums, int lower, int upper) {
		Arrays.sort(nums);
		long ans = 0;
		for (int j = 0; j < nums.length; j++) {
			// 注意要在 [0, j-1] 中二分，因为题目要求两个下标 i < j
			int r = lowerBound(nums, j, upper - nums[j] + 1);
			int l = lowerBound(nums, j, lower - nums[j]);
			ans += r - l;
		}
		return ans;
	}
	private int lowerBound(int[] nums, int right, int target) {
		int left = -1;
		while (left + 1 < right) {
			int mid = (left + right) >>> 1;
			if (nums[mid] >= target) {
				right = mid;
			} else {
				left = mid;
			}
		}
		return right;
	}


}
